package com.gxc.array;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个可能含重复值的数组arr，找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1)，
 * 返回所有的位置信息。
 */
public class GetNearLess2 {

    public static void main(String[] args) {
        int[] nums = {3, 4, 1, 5, 6, 2, 7};
        int[][] list = handle(nums);

        for (int i = 0; i < list.length; i++) {
            for (int j = 0; j < list[i].length; j++) {
                System.out.print(list[i][j] + " ");
            }
            System.out.println(" ");
        }
    }

    //单调栈内 用list 保存相同 value
    private static int[][] handle(int[] nums) {
        int[][] arr = new int[nums.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i]<nums[stack.peek().get(0)]) {
                List<Integer> popList = stack.pop();
                for (int j = 0; j < popList.size(); j++) {
                    Integer pop = popList.get(j);
                    arr[pop][1] = i;
                    if (stack.isEmpty()) {
                        arr[pop][0] = -1;
                    } else {
                        arr[pop][0] = stack.peek().get(stack.peek().size()-1);
                    }
                }

            }
            if (!stack.isEmpty() && nums[i] == nums[stack.peek().get(0)]) {
                stack.peek().add(i);
            } else {
                List<Integer> list = new LinkedList<>();
                list.add(i);
                stack.push(list);
            }

        }
        while (!stack.isEmpty()) {
            List<Integer> popList = stack.pop();
            for (int i = 0; i < popList.size(); i++) {
                Integer pop = popList.get(i);
                arr[pop][1] = -1;
                if (stack.isEmpty()) {
                    arr[pop][0] = -1;
                } else {
                    arr[pop][0] = stack.peek().get(stack.peek().size()-1);
                }
            }

        }
        return arr;
    }
}
